// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

#include <stddef.h>
#include <stdlib.h>

#include "runtime_types.h"
#include "type.h"
#include "assert.h"
#include "map.h"
#include "mem_alloc.h"
#include "panic.h"

// Rehash MAP to a larger size.

static void
__go_map_rehash(struct __go_map *map)
{
	const struct __go_map_descriptor *descriptor;
	const struct __go_type_descriptor *key_descriptor;
	uintptr_t key_offset;
	size_t key_size;
	uintptr_t(*hashfn) (const void *, uintptr_t);
	uintptr_t old_bucket_count;
	void **old_buckets;
	uintptr_t new_bucket_count;
	void **new_buckets;
	uintptr_t i;

	descriptor = map->__descriptor;

	key_descriptor = descriptor->__map_descriptor->__key_type;
	key_offset = descriptor->__key_offset;
	key_size = key_descriptor->__size;
	hashfn = key_descriptor->__hashfn;

	old_bucket_count = map->__bucket_count;
	old_buckets = map->__buckets;

	new_bucket_count = __go_map_next_prime(old_bucket_count * 2);
	new_buckets = (void **)runtime_malloc(new_bucket_count * sizeof(void *));
	__builtin_memset(new_buckets, 0, new_bucket_count * sizeof(void *));

	for (i = 0; i < old_bucket_count; ++i) {
		char *entry;
		char *next;

		for (entry = old_buckets[i]; entry != NULL; entry = next) {
			size_t key_hash;
			size_t new_bucket_index;

			// We could speed up rehashing at the cost of memory space
			// by caching the hash code.
			key_hash = hashfn(entry + key_offset, key_size);
			new_bucket_index = key_hash % new_bucket_count;

			next = *(char **)entry;
			*(char **)entry = new_buckets[new_bucket_index];
			new_buckets[new_bucket_index] = entry;
		}
	}

	runtime_free(old_buckets);

	map->__bucket_count = new_bucket_count;
	map->__buckets = new_buckets;
}

// Find KEY in MAP, return a pointer to the value.  If KEY is not
// present, then if INSERT is false, return NULL, and if INSERT is
// true, insert a new value and zero-initialize it before returning a
// pointer to it.

void *
__go_map_index(struct __go_map *map, const void *key, _Bool insert)
{
	const struct __go_map_descriptor *descriptor;
	const struct __go_type_descriptor *key_descriptor;
	uintptr_t key_offset;
	_Bool(*equalfn) (const void *, const void *, uintptr_t);
	size_t key_hash;
	size_t key_size;
	size_t bucket_index;
	char *entry;

	if (map == NULL) {
		if (insert)
			runtime_panicstring("assignment to entry in nil map");
		return NULL;
	}

	descriptor = map->__descriptor;

	key_descriptor = descriptor->__map_descriptor->__key_type;
	key_offset = descriptor->__key_offset;
	key_size = key_descriptor->__size;
	__go_assert(key_size != 0 && key_size != -1UL);
	equalfn = key_descriptor->__equalfn;

	key_hash = key_descriptor->__hashfn(key, key_size);
	bucket_index = key_hash % map->__bucket_count;

	entry = (char *)map->__buckets[bucket_index];
	while (entry != NULL) {
		if (equalfn(key, entry + key_offset, key_size))
			return entry + descriptor->__val_offset;
		entry = *(char **)entry;
	}

	if (!insert)
		return NULL;

	if (map->__element_count >= map->__bucket_count) {
		__go_map_rehash(map);
		bucket_index = key_hash % map->__bucket_count;
	}

	entry = (char *)runtime_malloc(descriptor->__entry_size);
	__builtin_memset(entry, 0, descriptor->__entry_size);

	__builtin_memcpy(entry + key_offset, key, key_size);

	*(char **)entry = map->__buckets[bucket_index];
	map->__buckets[bucket_index] = entry;

	map->__element_count += 1;

	return entry + descriptor->__val_offset;
}
